package com.sicheng.lc.杂题.二分技巧;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/7/16 17:44
 */
public class 搜索旋转排序数组 {
    //https://leetcode.cn/problems/search-in-rotated-sorted-array/
    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0)
            return -1;
        int l = 0, r = nums.length - 1;
        if (nums[l] <= nums[r])
            return search(nums, target, l, r);
        int p = 0;
        while (l <= r) {
            int mid = l + r >> 1;
            if (nums[r] >= nums[l]) {
                p = r;
                break;
            }
            if (nums[mid] > nums[l]) {
                l = mid;
            } else if (nums[r] < nums[l]) {
                if (nums[mid] <= nums[r])
                    r = mid - 1;
                else
                    r = r - 1;
            }
        }

        if (target < nums[0])
            return search(nums, target, p + 1, nums.length - 1);
        return search(nums, target, 0, p);
    }

    public int search(int[] nums, int x, int L, int R) {
        int l = L, r = R;
        while (l <= r) {
            int mid = l + r >> 1;
            if (nums[mid] == x)
                return mid;
            if (nums[mid] > x) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        搜索旋转排序数组 s = new 搜索旋转排序数组();
        int[] nums = {3, 1};
        System.out.println(s.search(nums, 1));
    }
}
